Note: This final exam practice questions are developed based exclusively on the materials covered in the class so far, following the topics from Week 6 through Week 14.
Part 1: Multiple Choice Questions (20 Questions)
Instructions: Select the best answer.
Which principle defines the removal protocol for a standard Queue?
A. LIFO
B. LILO
C. FIFO
D. FILOWhat data structure is used as the collection in the generic graph traversal algorithm to perform a Breadth-First Traversal (BFS)?
A. Stack
B. List
C. Dictionary
D. QueueIn the context of graph implementation, which representation typically requires O(N²) memory, regardless of the number of edges (M)?
A. Adjacency List
B. Linked List of Edges
C. Adjacency Matrix
D. Hash MapA graph that contains no cycles is referred to as a(n):
A. Complete graph
B. Connected graph
C. Dense graph
D. Acyclic graphWhich type of binary tree traversal visits the root node after visiting both the left and right subtrees?
A. Inorder
B. Preorder
C. Level order
D. PostorderIf a binary tree is vine-like and contains N nodes, what is its maximum height?
A. log₂(N)
B. N+1
C. 1
D. N−1In a Priority Queue, if two items have the same priority, how are they removed?
A. Randomly
B. In FIFO order
C. Based on the insertion order
D. Based on priority rankWhich operation is used to add an item to the top of a Stack?
A. Pop
B. Peek
C. Push
D. AddWhat is the complexity of determining whether an edge exists between two given vertices using an Adjacency Matrix representation?
A. O(N)
B. O(N²)
C. O(log N)
D. O(1) (Constant time)What is the fundamental structure used to manage function and method calls in computer memory?
A. The Object Heap
B. The Data Segment
C. The Instruction Pointer
D. The Call StackThe initialization step of Dijkstra’s shortest path algorithm is analyzed to have what time complexity, where N is the number of vertices?
A. O(N³)
B. O(N)
C. O(N²)
D. O(M)When evaluating a postfix expression using a stack, what action is taken when an operand is encountered?
A. It is ignored.
B. It is applied to the two preceding operands.
C. It is pushed onto the operand stack.
D. It is appended to the postfix expression.A Directed Acyclic Graph (DAG) is commonly used to model processes involving:
A. Mutual relationships (like road networks)
B. Network cycles
C. Dependencies (like scheduling tasks)
D. Fully connected systemsIn a Min-Heap, where is the smallest data item always located?
A. At the last level, leftmost position
B. At the root
C. Near the leaf nodes
D. At the rightmost nodeWhen implementing a Queue using a circular array, what is the running time complexity for both the add and pop operations?
A. O(N)
B. O(logN)
C. O(1)
D. O(N²)Which specific type of tree is defined by the property that the key in each node is greater than all keys in its left subtree and less than all keys in its right subtree?
A. Expression Tree
B. Min-Heap
C. Full Binary Tree
D. Binary Search Tree (BST)What specialized structure is used to implement a priority queue when the implementation uses a min-heap?
A. Linked List
B. Array Stack
C. Complete Binary Tree
D. Adjacency ListWhen converting an infix expression to a postfix expression, what happens to an opening parenthesis ( when encountered?
A. It is discarded immediately.
B. It is appended to the postfix expression.
C. It is pushed onto the stack.
D. It forces all pending operators to be popped.What term is used for a subgraph that includes all the vertices of the original connected, undirected graph, and is also acyclic?
A. Connected Component
B. Depth-First Search Tree
C. Spanning Tree
D. Directed GraphA vertex in a graph that has a degree of 0 is called a(n):
A. Successor
B. Neighbor
C. Isolated vertex
D. Root
Part 2: Short Answer Questions (1-2 Words) (10 Questions)
What data structure is used to implement the collection in a Depth-First Traversal (DFS)?
What term describes the value used to label an edge in a weighted graph?
What name is given to a path that does not pass through the same vertex more than once?
In the context of the LinkedDirectedGraph implementation, what type of Python data structure maintains the mapping between vertex labels and corresponding vertex objects?
What is the term for a node in a tree that has no children?
What type of tree structure is defined by the property that all levels are fully filled except possibly the last, which is filled from left to right?
What is the main technique used by operating systems for fair allocation of CPU resources among processes waiting in a queue?
The length of a path in a graph is defined as the number of what?
What is the name of the general algorithmic technique that incrementally builds candidates to solutions and abandons them as soon as they cannot lead to a valid solution?
Which type of queue allows items of higher rank to be removed before those of lower rank?
Part 3: Applied Questions (5 Questions)
2. Scenario: Compiler Optimization
A compiler is processing a complex arithmetic expression: ((4 + 5) 6) - 3.*
Query: Describe the sequence of steps a stack-based algorithm would perform to evaluate the Postfix equivalent of this expression. Use only the operators and operands from the expression above. Explain what happens to the stack when the first operator * is encountered in the Postfix evaluation process.
3. Scenario: Airline Route Mapping
An airline wants to find the cheapest route between its hub city (S) and all other available cities (V). The cost of flying between any two cities (edges) is always positive. The total number of cities (N) is 100.
Query: Which algorithm—Dijkstra’s or Floyd’s—is appropriate for this task, and what is the computational complexity of the chosen algorithm? Justify your choice based on the problem requirements and time complexity.
4. Scenario: Emergency Room Scheduling
You are designing the ERModel for an Emergency Room Scheduler system, which must manage patients based on priority (Critical=1, Serious=2, Fair=3).
Query: If you use a LinkedPriorityQueue implementation based on a sorted linked list, how does the add method ensure that a new patient item is placed correctly? If the queue currently holds [Patient_A (1), Patient_B (2), Patient_C (2), Patient_D (3)], where would a new patient, Patient_E (2), be inserted, and why?
5. Scenario: Tree Structure Verification
A student has implemented the LinkedBST class and wants to check its integrity by analyzing the visitation order of nodes. The tree contains nodes labeled 10, 5, 15, 3, 7, 12, 18.
Query: Provide the expected node visitation order for the Inorder Traversal and explain why this traversal is particularly useful for verifying a Binary Search Tree (BST).